Задача #A0080

Память 16 MB Время 1000 ms Сложность 25 %

Qutilarni joylashtirish

MegaBoy yaqinda bir korxonaga ishga kirdi. Uning vazifasi qutilarni to'g'ri joylashtirish. Qutilar 1 dan n gacha raqamlangan. Ular to'g'ri joylashtirilgan hisoblanadi qachonki ularda hech qanday yonma-yon toq yoki juft qutilar bo'lmasa va tartib raqami bo'yicha o'sish tartibida joylashgan bo'lsa. Unda 1 dan n gacha raqamlangan n ta quti bor ularni to'g'ri joylashtirish mumkin bo'lgan barcha variantlar sonini toping.

Входные данные:

Kirish faylida yagona qatorda \(n(1\le n \le 10^6)\) soni kiritiladi.

Выходные данные:

Chiqish faylida barcha variantlar sonini chop eting. Bunda javob juda katta bo'lishi mumkin shu sababdan 1000000007 ga bo'lgandagi qoldiqni chop eting.

Примеры

#	input.txt	output.txt
1	3	6
2	4	11

Примечание:

n = 3 bo'lgand:

1
2
3
1 2
2 3
1 2 3

Jami 6 xil

n = 4 bo'lganda

1
2
3
4
1 2
2 3
3 4
1 4
1 2 3
2 3 4
1 2 3 4

Telegram Facebook

Отправить решение

Пожалуйста, войдите в систему, чтобы выполнить это действие,если у вас нет учетной записи, вы можете зарегистрироваться в любое время